Recently, there has been an increase in the need for systems that can protect digital data from eavesdropping, forging, and other forms of attack. As more commercial transactions and communications are handled with digital electronics, the need will increase. Additionally, the increasing sophistication of adversaries exacerbates the problem of protecting digital data.
A variety of schemes have been developed for protecting and authenticating data. The problem now faced by many is to choose a scheme from among the many that will be both secure and economical. Traditionally, printed information has been authenticated by appending the handwritten signature of a person or persons to the printed material. Modern methods for authenticating data proceed in a similar manner, except that the handwritten signature is replaced by a digital signature. In many cases, this signature consists of a set of bits that are computed by the signer based on the message being signed.
A digital signature scheme is an important primitive to secure digital communication in its own right. Moreover, it is also used as a building block for higher level cryptographic scheme such as anonymous credentials, electronic voting, group signature, etc. In such constructions, signatures are often issued on hidden messages or knowledge of a signature is proved in zero-knowledge without the value of the signature being revealed. While such tasks can be done for any signature scheme, if they need to be done efficiently, a signature scheme needs to have additional properties.
Ideally, anyone is able to verify the digital signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature.
One of the first schemes proposed that provides such feature is by Camenisch and Lysyanskaya, where one can use so-called generalized Schnorr-proofs to efficiently prove knowledge of a signature without revealing the signature or the messages. Their scheme was used to construct many cryptographic protocols and since a number of alternative signature schemes have been proposed that other similar advantages. However, for all of these signature schemes, two party protocols are requires to issue a signature on an encrypted or committed message.
As a result of the current state of the prior art, there remains a long felt need for provably fast and secure digital signature schemes.